package com.alex.space.commons.tree;

import java.util.Random;

/**
 * 二叉搜索树
 *
 * @author Alex
 * Created by Alex on 2018/3/13.
 */
public class BinarySortTree {

	public static void main(String[] args) {
		TreeNode root = TreeNode.builder().data(6).build();
		root.left = TreeNode.builder().data(4).build();
		root.right = TreeNode.builder().data(7).build();
		root.left.left = TreeNode.builder().data(2).build();
		root.left.right = TreeNode.builder().data(5).build();
		root.right.right = TreeNode.builder().data(10).build();
		TreeUtils.inOrderReverse(root);

		insertBST(root, new Random().nextInt(10));

		deleteBST(root, new Random().nextInt(10));

	}

	private static boolean searchBST(TreeNode root, int key) {
		if (root.data == key) {
			return true;
		} else if (root.data > key && root.left != null) {
			return searchBST(root.left, key);
		} else if (root.data < key && root.right != null) {
			return searchBST(root.right, key);
		}

		return false;
	}

	private static void insertBST(TreeNode root, int key) {
		if (!searchBST(root, key)) {
			TreeNode tmp = root;
			TreeNode parent = root;

			while (tmp != null) {
				parent = tmp;
				if (key < tmp.data) {
					tmp = tmp.left;
				} else {
					tmp = tmp.right;
				}
			}

			tmp = TreeNode.builder().data(key).build();
			if (parent.data > tmp.data) {
				parent.left = tmp;
			} else {
				parent.right = tmp;
			}
		}

		TreeUtils.inOrderReverse(root);
	}

	private static void deleteBST(TreeNode root, int key) {
		if (root == null) {
			return;
		}

		//用来保存待删除节点
		TreeNode cur = root;
		//用来保存待删除节点的父亲节点
		TreeNode parent = root;
		boolean curIsLeft = true;

		while (cur != null && cur.data != key) {
			parent = cur;

			if (key < cur.data) {
				cur = cur.left;
				curIsLeft = true;
			} else {
				cur = cur.right;
				curIsLeft = false;
			}
		}

		// 没找到要删除的节点
		if (cur == null) {
			return;
		}

		// 叶子节点
		if (cur.left == null && cur.right == null) {
			if (curIsLeft) {
				parent.left = null;
			} else {
				parent.right = null;
			}
		}

		// 有一个子节点
		else if (cur.left == null || cur.right == null) {
			if (curIsLeft) {
				parent.left = cur.left == null ? root.right : root.left;
			} else {
				parent.right = cur.left == null ? root.right : root.left;
			}
		}

		// 有两个子节点
		else {

			TreeNode minInRight = cur.right;
			//用来保存待删除节点的直接后继节点的父亲节点
			TreeNode minParentNode = cur;

			while (minInRight.left != null) {
				minParentNode = minInRight;
				minInRight = minInRight.left;
			}

			cur.data = minInRight.data;
			if (minInRight.data != cur.right.data) {
				minParentNode.left = null;
			} else {
				cur.right = null;
			}

		}

		TreeUtils.inOrderReverse(root);
	}
}
